Needleman and Wunsch proposed a general scheme for the similarity of two amino acids. Their algorithm evaluates the significance of the obtained maximum match based on the probability that this match occurs among random sequences. The value of cell M[i; j] of dynamic programming (DP) lattice is the maximum among M[i + 1; j + 1..n] and M[i +1..m; j + 1], plus 1 if ai = bj . So the time complexity is O(m2n + mn2).
int NeedlemanWunsch_Alg(char *stringA, char *stringB, int m, int n)
{
int i, j, ti, tj, max, **tab;
tab = (int**)calloc((m + 1), sizeof(int*));
for (i = 0; i <= m; i++){
tab[i] = (int*)calloc((n + 1), sizeof(int));
}
for (i = 1; i <= m; i++){//initialize tab
for (j = 1; j <= n; j++){
if (stringA[i] == stringB[j]){
tab[i][j] = 1;
}
}
}
for (i = 1; i <= m; i++){
for (j = 1; j <= n; j++){
max = 0;
if (i != 1){
ti = i - 1;
for (tj = j - 1; tj > 0; tj--){
if (tab[ti][tj] > max){
max = tab[ti][tj];
}
}
}
if (j != 1){
tj = j - 1;
for (ti = i - 1; ti > 0; ti--){
if (tab[ti][tj] > max){
max = tab[ti][tj];
}
}
}
tab[i][j] += max;
}
}
max = 0;
for (i = m; i > 0; i--)
{
if (tab[i][n] > max)
max = tab[i][n];
}
for (j = n; j > 0; j--)
{
if (tab[m][j] > max)
max = tab[m][j];
}
return max;
}